import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test55 {
    static class Trie {
        Map<String, List<String>> hash;

        public Trie() {
            hash = new HashMap<>();
        }

        public void insert(String word) {
            hash.put(word,new ArrayList<>());
            for(String key : hash.keySet()) {
                if(key.startsWith(word)) {
                    // 如果key也有这个前缀，那么 word也有，所以全部添加
                    hash.get(word).addAll(hash.get(key));
                }
            }
        }

        public boolean search(String word) {
            // 检查 word 是否存在
            return hash.containsKey(word);
        }

        public boolean startsWith(String prefix) {
            // 检查是否有 key 以 prefix 开头
            for (String key : hash.keySet()) {
                if (key.startsWith(prefix)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        // 定义操作序列
        String[] operations = {"Trie", "insert", "search", "search", "startsWith", "insert", "search"};
        // 定义对应的参数
        String[][] params = {{}, {"apple"}, {"apple"}, {"app"}, {"app"}, {"app"}, {"app"}};

        // 存储结果
        List<Object> result = new ArrayList<>();
        // Trie 对象
        Trie trie = null;

        // 遍历操作序列
        for (int i = 0; i < operations.length; i++) {
            String op = operations[i];
            switch (op) {
                case "Trie":
                    trie = new Trie();
                    result.add(null);
                    break;
                case "insert":
                    trie.insert(params[i][0]);
                    result.add(null);
                    break;
                case "search":
                    boolean searchResult = trie.search(params[i][0]);
                    result.add(searchResult);
                    break;
                case "startsWith":
                    boolean startsWithResult = trie.startsWith(params[i][0]);
                    result.add(startsWithResult);
                    break;
            }
        }

        // 输出结果
        System.out.println(result);
    }
}